package 力扣算法练习.main1.part1;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class day17 {
    /*
    给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
    https://leetcode.cn/problems/permutations/
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result=new ArrayList<>();
        if (nums.length==0)return result;
        Deque<Integer> temp=new ArrayDeque<>();//记录一种排序的可能
        boolean[] flag=new boolean[nums.length];//记录已经出现过的数字
        pfs(nums,nums.length,0,flag,temp,result);
        return result;
    }

    private void pfs(int[] nums, int length, int steps, boolean[] flag, Deque<Integer> temp, List<List<Integer>> result) {
        if (steps==length){
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < length; i++) {
            if (flag[i])continue;
            temp.addLast(nums[i]);
            flag[i]=true;
            pfs(nums,length,steps+1,flag,temp,result);
            temp.removeLast();
            flag[i]=false;
        }
    }
}
